package ljl.codetop300;

import commons.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;

public class _445_add_2 {

  /**
   * 1-2-3
   * 4-5
   * 这种的，感觉递归没法做，反转再加吧
   */
  static class try1 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      l1 = reverse(l1);
      l2 = reverse(l2);
      ListNode head = null;
      int carry = 0;
      while (l1 != null || l2 != null || carry != 0) {
        int v1 = l1 == null ? 0 : l1.val;
        int v2 = l2 == null ? 0 : l2.val;
        int sum = v1 + v2 + carry;
        ListNode node = new ListNode(sum % 10);
        node.next = head;
        head = node;
        carry = sum / 10;
        l1 = l1 == null ? null : l1.next;
        l2 = l2 == null ? null : l2.next;
      }
      return head;
    }

    ListNode reverse(ListNode node) {
      ListNode pre = null;
      while (node != null) {
        ListNode next = node.next;
        node.next = pre;
        pre = node;
        node = next;
      }
      return pre;
    }
  }

  static class off {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      Deque<Integer> stack1 = new ArrayDeque<>();
      Deque<Integer> stack2 = new ArrayDeque<>();
      while (l1 != null) {
        stack1.push(l1.val);
        l1 = l1.next;
      }
      while (l2 != null) {
        stack2.push(l2.val);
        l2 = l2.next;
      }
      int carry = 0;
      ListNode ans = null;
      while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
        int a = stack1.isEmpty() ? 0 : stack1.pop();
        int b = stack2.isEmpty() ? 0 : stack2.pop();
        int cur = a + b + carry;
        carry = cur / 10;
        cur %= 10;
        ListNode curnode = new ListNode(cur);
        curnode.next = ans;
        ans = curnode;
      }
      return ans;
    }
  }
}
